﻿#include <iostream>
using namespace std;

const int MAX = 1000;				//假定边上的权值均不超过1000
const int n = 10;

int arc[n][n] = {					
	MAX, 4,   2,   3,   MAX, MAX, MAX, MAX, MAX, MAX,
	4,   MAX, MAX, MAX, 9,   8,   MAX, MAX, MAX, MAX,
	2,   MAX, MAX, MAX, 6,   7,   8,   MAX, MAX, MAX,
	3,   MAX, MAX, MAX, MAX, 4,   7,   MAX, MAX, MAX,
	MAX, 9,   6,   MAX, MAX, MAX, MAX, 5,   6,   MAX,
	MAX, 8,   7,   4,   MAX, MAX, MAX, 8,   6,   MAX,
	MAX, MAX, 8,   7,   MAX, MAX, MAX, 6,   5,   MAX,
	MAX, MAX, MAX, MAX, 5,   8,   6,   MAX, MAX, 7,
	MAX, MAX, MAX, MAX, 6,   6,   5,   MAX, MAX, 3,
	MAX, MAX, MAX, MAX, MAX, MAX, MAX, 7,   3,   MAX
};

int backPath(){						//求n个顶点的多段图的最短路径
	int i, j, temp;
	int cost[n], path[n];			//存储路径长度和路径
	for(i = 1; i < n; i++){			//初始化路径长度为MAX
		cost[i] = MAX;
		path[i] = -1;
	}
	cost[0] = 0; path[0] = -1;		//顶点0为源点
	for(j = 1; j < n; j++){			//执行填表工作
		for(i = j - 1; i >= 0; i--){//考察顶点的所有入边
			if(arc[i][j] + cost[i] < cost[j]){
				cost[j] = arc[i][j] + cost[i];
				path[j] = i;
			}
		}
	}
	cout << n - 1;					//输出终点
	i = n - 1;
	while(path[i] >= 0){			//依次输出path[i]
		cout << "<-" << path[i];
		i = path[i];				//求得路径上顶点i的前一个顶点
	}
	
	return cost[n - 1];				//返回最短路径长度
}

int main(){
	cout << endl << "多短图最短路径为：" << backPath() << endl;
	
	system("pause");
	return 0;
}